# -*- coding: utf-8 -*-

"""剑指 Offer II 102. 加减的目标值
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：
输入：nums = [1], target = 1
输出：1

提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000"""

class Solution:
    """回溯：遍历到一个数，都有两种选择，要么做加法，要么做减法，并将结果传到下一回
    动态规划：遍历到一个数，都有若干种运算结果，且每个运算结果都有一定数量的路径，这种状态是确定的。
    所以用哈希字典来表示状态"""
    def findTargetSumWays(self, nums, target: int) -> int:
        answer = {0:1}
        for n in nums:
            dp = {}
            for t, count in answer.items():
                total = t + n
                if total in dp:
                    dp[total] += count
                else:
                    dp[total] = count
                total = t - n
                if total in dp:
                    dp[total] += count
                else:
                    dp[total] = count
            answer = dp
        return answer.get(target, 0)


if __name__ == '__main__':
    so = Solution()
    print(so.findTargetSumWays(nums = [1,1,1,1,1], target = 3))
    print(so.findTargetSumWays(nums = [1], target = 1))
    print(so.findTargetSumWays(nums = [1], target = 2))
